def insertion_sort(arr):
    n=len(arr)
    # 外循环：已排序区间为 [0, i-1]
    for i in range(1,n):
        insert_idx=0
        value=arr[i]
        for j in range(i-1,-1,-1):
            # 元素后移
            if arr[j]>value:
                arr[j+1]=arr[j]
            else:
                insert_idx=j+1
                break
        a[insert_idx]=value


def insert_sort(arr):
    n=len(arr)
    for i in range(1,n):
        value=arr[i]
        j=i-1
        while j>=0 and arr[j]>value:
            arr[j+1]=arr[j]
            j-=1
        # 当arr[j]<=value时，需要在arr[j]的后面插入
        arr[j+1]=value

a = [4, 3, 5, 2, 1]
insert_sort(a)
print(a)